#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution
{
public:
    // "|(&(t,f,t),!(t))"
    bool parseBoolExpr(string expression)
    {
        int n = expression.size();
        vector<char> st = {};
        for (int i = 0; i < n; i++)
        {
            if (expression[i] == ',')
                continue;
            else if (expression[i] != ')')
            {
                st.push_back(expression[i]);
                continue;
            }
            else
            {
                int t = 0, f = 0;
                while (!st.empty() && st.back() != '(')
                {
                    if (st.back() == 't')
                        t++;
                    else
                        f++;
                    st.pop_back();
                }
                st.pop_back();
                char op = st.back();
                st.pop_back();
                switch (op)
                {
                case '!':
                    st.push_back(t == 1 ? 'f' : 't');
                    break;
                case '&':
                    st.push_back(f > 0 ? 'f' : 't');
                    break;
                case '|':
                    st.push_back(t > 0 ? 't' : 'f');
                    break;
                }
            }
        }
        return st.back() == 't';
    }
};